CSEG8003 Course home Portal
UPES · School of Computer Science
CSEG8003 — Modelling and Simulation · L-T-P-C 2-0-1-3
Unit II
Dynamical, Finite State and Complex Model Simulations
7 lecture hours · Theory notes · Dr. Mohsin Furkh Dar
CO1CO3 Networks Actors & meshes Agents & CA Monte Carlo Complex adaptive systems
How this unit fits

Unit I asked how does the clock advance. This unit asks what shape does the state have. Each modelling paradigm below is essentially a different answer to one question: what is an entity, and who is it coupled to?

  • Coupled through edges → graph/network simulations (Section 1).
  • Coupled through messages → actor-based (Section 2).
  • Coupled through shared geometry → mesh-based (Section 3).
  • Coupled through local neighbourhoods on a lattice → cellular automata (Section 6).
  • Coupled through perception, decision and environment → agent-based (Section 5).
  • Not coupled at all — independent samples → Monte Carlo (Section 7).

Learn that mapping and every comparison question in this unit becomes answerable.

1. Graph or Network Transition Based Simulations

Definition

A graph-based (network transition) simulation represents the system as a graph G = (V, E) in which nodes carry state and edges define who may influence whom; the simulation repeatedly applies transition rules that update node (or edge) states as a function of the states of their neighbours.

The structure of the graph is not a detail of the implementation — it is a first-class part of the model. Two populations with identical infection probabilities but different contact-network topologies produce completely different epidemics, and that is exactly the insight this paradigm exists to capture.

1.1 Ingredients of a network model

  1. Topology — who is connected to whom; static or evolving; directed or undirected; weighted or unweighted.
  2. Node state — from a finite set (S, I, R; on/off; opinion in {0,1}) or continuous (voltage, load, temperature).
  3. Transition rule — deterministic or probabilistic function of the node's state and its neighbours' states.
  4. Update scheme — synchronous (all nodes at once) or asynchronous (one random node at a time). This choice changes the results, not merely the speed.
  5. Observables — epidemic size, time to consensus, fraction of nodes failed, size of the largest connected component.

1.2 Standard network topologies

Table 2.1 — Network families used in simulation studies.
Family Construction Characteristic properties
Regular lattice Each node joined to its k nearest neighbours on a grid or ring High clustering, long average path length; slow spreading.
Erdős–Rényi random Each of the possible edges present with probability p Poisson degree distribution, short paths, low clustering; a giant component appears at p = 1/n.
Watts–Strogatz small world Lattice with a fraction of edges randomly rewired High clustering and short paths — the “six degrees” regime; a few long-range links dramatically accelerate spreading.
Barabási–Albert scale free Growth with preferential attachment Power-law degrees P(k) ∝ k−γ ; hubs; robust to random failure but fragile to targeted attack.
Spatial / geometric Nodes placed in space, joined within a radius Realistic for wireless, power and road networks.
Empirical Measured from data (call records, autonomous systems, citations) Most realistic but sampled, incomplete and privacy-sensitive.

1.3 The canonical example: epidemic spreading (SIR on a network)

Example — network SIR

Each node is Susceptible, Infected or Recovered. In each discrete step:

  • every infected node i infects each susceptible neighbour independently with probability β;
  • every infected node recovers with probability γ.

The mean-field (well-mixed) version of this model has the epidemic threshold R0 = β/γ = 1. On a network with degree distribution of mean ⟨k⟩ and second moment ⟨k2⟩, the threshold becomes

βc/γ = ⟨k⟩ / (⟨k2⟩ − ⟨k⟩)

For a scale-free network with γ ≤ 3 the second moment diverges as the network grows, so the threshold tends to zero: on a hub-dominated network, even a weakly infectious disease spreads. This single result is why network structure is modelled at all, and it makes an excellent 10-mark answer.

1.4 Other applications and implementation notes

Implementation: adjacency lists for sparse graphs; keep an active set of infected/changed nodes so that the cost per step is O(edges incident to active nodes) rather than O(|E|); use the Gillespie algorithm for a continuous-time formulation; and average over many random graph realisations and many stochastic runs, since both the topology and the dynamics are random.

Common mistake

Reporting results from a single generated random graph. Two sources of randomness exist — the graph and the dynamics — and both must be replicated, otherwise the confidence interval is meaningless.

2. Actor-Based Simulations

Definition — Actor model

An actor is a computational entity that has private state, a mailbox, and a behaviour; in response to a message an actor may (i) send finitely many messages to actors it knows, (ii) create finitely many new actors, and (iii) designate the behaviour to be used for the next message. Actors share nothing; all interaction is by asynchronous message passing.

Actor-based simulation takes this concurrency model (Hewitt, 1973) as its modelling formalism. It is the natural bridge between a discrete-event model and a parallel implementation, because “no shared state” removes the data races that otherwise dominate parallel simulation (Unit III).

2.1 Properties that matter for simulation

  1. Encapsulation. An actor's state can be changed only by the actor itself, which makes the model's causality explicit and auditable.
  2. Asynchrony. Sending is non-blocking; the sender continues immediately. This naturally models systems in which communication takes time.
  3. Location transparency. An actor addresses another by identity, not by memory address, so actors can be migrated between cores or machines for load balance.
  4. Fair, unbounded delivery. Messages are eventually delivered but order between different senders is not guaranteed — in simulation this must be tightened by timestamps, or results become irreproducible.
  5. Supervision. Actor frameworks (Erlang/OTP, Akka) provide “let-it-crash” supervision trees, which map neatly onto fault-tolerance experiments.

2.2 Actor simulation versus plain discrete-event simulation

A DES has one global event list; an actor simulation has many local queues. That is precisely what makes actors parallelisable and DES hard to parallelise. The price is that global ordering must be reconstructed: each message carries a timestamp, each actor keeps its own logical clock, and a synchronisation protocol (conservative null-messages or optimistic Time Warp, Unit III) guarantees that no actor processes a message out of timestamp order.

Example — actor model of a call centre

Actors: Caller, Router, Agent, Supervisor. A Caller sends Request(t) to Router; the router forwards to a free Agent or enqueues; the agent replies Done(t') and asks the router for the next call. Adding a second call centre is simply adding actors — no shared queue data structure has to be redesigned, and the same code runs on one core or on a cluster.

2.3 Strengths, weaknesses, tools

3. Mesh-Based Simulations

Definition

A mesh-based simulation discretises a continuous spatial domain into a finite set of cells, elements or grid points (the mesh), approximates the governing partial differential equations on that mesh, and advances the resulting system of algebraic or ordinary differential equations in time.

This is the workhorse of computational science: fluid dynamics, structural mechanics, heat transfer, electromagnetics, weather and climate. It is also the paradigm that consumes the world's largest supercomputers, which is why Unit III's partitioning material is written mainly with meshes in mind.

3.1 Mesh types

3.2 Discretisation methods

Table 2.2 — The three classical discretisation families.
Method Idea Typical use
Finite difference (FDM) Replace derivatives by difference quotients on a structured grid Simple geometry; heat equation, wave equation, teaching examples
Finite volume (FVM) Integrate the conservation law over each control volume; fluxes across faces CFD; conserves mass/momentum/energy exactly by construction
Finite element (FEM) Expand the solution in basis functions over elements; minimise a weighted residual Structural mechanics, complex geometry, higher-order accuracy
Example — explicit FDM for the 2-D heat equation

∂T/∂t = α∇2T on a uniform grid of spacing h becomes the five-point stencil

Ti,jn+1 = Ti,jn + (αΔt /h2)(Ti+1,j + Ti−1,j + Ti, j+1 + Ti,j−1 − 4Ti,j)

which is stable only for αΔt/h2 ≤ 1/4 in two dimensions. Note the consequence: halving h forces Δt down by four, so total work rises by a factor of 16 — the reason mesh simulations need supercomputers.

3.3 Practical concerns

  1. Mesh quality (aspect ratio, skewness) governs accuracy and solver convergence far more than the number of cells does.
  2. Boundary conditions — Dirichlet (value), Neumann (flux), periodic; wrong boundary treatment is the most common source of nonsense results.
  3. Stability conditions — CFL condition for explicit advection: uΔt/Δx ≤ 1.
  4. Convergence study — the result must be shown to be mesh-independent by refining until the answer stops changing.
  5. Halo / ghost cells — when the mesh is split across processors, each partition keeps a copy of its neighbours' boundary layer; exchanging haloes is the dominant communication cost (Unit III).

4. Hybrid Simulations

Definition

A hybrid simulation combines two or more simulation paradigms — typically system dynamics (continuous), discrete-event, and agent-based — inside one model so that each subsystem is represented in the formalism that fits it, with defined interfaces translating state between them.

4.1 The three-paradigm view

Table 2.3 — The three paradigms usually combined in hybrid models.
Paradigm Level of abstraction Represents
System dynamics Strategic / aggregate Stocks, flows, feedback loops, delays; no individuals at all
Discrete event Tactical / operational Passive entities flowing through a process of queues and resources
Agent based Any, usually operational Active, decision-making individuals with behaviour and interaction

4.2 Interface patterns and their pitfalls

  1. Continuous → discrete: a threshold crossing fires an event. Requires zero-crossing detection with root finding (Unit I, Section 3.3).
  2. Discrete → continuous: an event changes a rate or a coefficient of the ODE, so the integrator must be restarted at that instant rather than stepping across it.
  3. Aggregate ↔ individual: converting a stock of 12.6 patients into agents forces rounding; do it stochastically to avoid systematic bias.
  4. Clock reconciliation: one sub-model steps at fixed Δt, the other jumps between events; the coupling interval must be defined explicitly and both models must be synchronised at those instants.
Example — hybrid model of a hospital during an outbreak
  • System dynamics: community infection prevalence (stocks S, I, R with flows).
  • Agent based: patients with individual severity, comorbidity and behaviour, who decide when to seek care.
  • Discrete event: the hospital itself — triage, beds, ICU, staff shifts as resources and queues.

Prevalence drives the arrival rate of agents; the hospital's admission decisions feed back into the community model as isolation. No one paradigm could represent all three layers honestly.

Exam tip

When asked to justify a hybrid model, always argue from the question, not from the technology: state which sub-question needs individual detail, which needs aggregate feedback, and which needs resource contention. Then map each to its paradigm.

5. Agent-Based and Multi-Agent Simulations

Definition

An agent-based model (ABM) represents a system as a population of autonomous agents, each with internal state and behavioural rules, situated in an environment, and studies the emergent system-level behaviour that arises from their local interactions.

A multi-agent system (MAS) emphasises agents that are additionally goal-directed and often cognitive — they reason, negotiate, cooperate or compete to achieve objectives.

5.1 Properties of an agent

  1. Autonomy — controls its own state and actions; nobody schedules it centrally.
  2. Situatedness — lives in an environment (grid, network, continuous space, GIS map) that it perceives and modifies.
  3. Local perception — sees only a neighbourhood, never the global state.
  4. Heterogeneity — agents may differ in attributes, rules and goals; this is the key advantage over compartment models.
  5. Interaction — with other agents (directly, or indirectly through the environment, as in ant pheromone trails — stigmergy).
  6. Adaptivity (optional) — learning, memory, or evolution of rules.
Definition — Emergence

Emergence is the appearance of system-level structure or behaviour that is not programmed into any individual agent and cannot be read off from the individual rules: traffic jams from car-following rules, flocks from three steering rules, segregation from a mild neighbour preference.

5.2 Classical models worth naming in an answer

5.3 Agent architectures

5.4 Multi-agent coordination mechanisms

When agents must act together, MAS supplies the mechanisms: contract net protocol for task allocation, auctions for resource allocation, voting and argumentation for group decisions, game-theoretic equilibria for competition, and norms and institutions for constraining behaviour. FIPA-ACL standardises the message semantics.

5.5 Strengths, limitations and reporting

Table 2.4 — Agent-based modelling: what you gain and what it costs.
Strengths Limitations
Captures heterogeneity and individual history Many parameters, often unmeasurable, so calibration is hard
Represents space, networks and local interaction naturally Computationally heavy; population size limits realism
Generates emergent phenomena the modeller did not encode Emergence can also be an artefact of update order or grid geometry
Rules are expressed in the domain expert's own language Validation is difficult: matching one aggregate curve does not validate the mechanism
Ideal for policy “what-if” experiments Stochastic and path dependent — needs many replications and sensitivity analysis
Common mistake

Publishing a single, visually appealing run of an ABM as evidence. An ABM result is a distribution over runs, and the accepted reporting standard is the ODD protocol (Overview, Design concepts, Details) plus a sensitivity analysis. Mention ODD whenever an examiner asks how ABM results should be reported.

6. Cellular Automata Based Simulations

Definition

A cellular automaton (CA) is a discrete dynamical system defined by a regular lattice of cells, a finite set of states, a neighbourhood template, and a local transition rule applied uniformly and synchronously to every cell; the global behaviour emerges purely from repeated local updates.

Formally a CA is the quadruple (L, S, N, f) — lattice, state set, neighbourhood, rule — plus a boundary condition (periodic, fixed or reflecting).

6.1 Neighbourhoods and rules

6.2 Wolfram's four classes

  1. Class I — evolves to a homogeneous fixed state.
  2. Class II — settles into simple periodic or stable local structures.
  3. Class III — chaotic, aperiodic, random-looking patterns.
  4. Class IV — complex localised structures that interact; the “edge of chaos”, capable of universal computation.

6.3 Applying CA to physical systems

Example — forest-fire propagation (your Experiment 5)

States: EMPTY, TREE, BURNING, BURNT. Rules applied synchronously each step:

  1. BURNING → BURNT.
  2. TREE with at least one BURNING neighbour → BURNING with probability pspread, weighted by wind direction and slope.
  3. TREE → BURNING with small probability f (lightning).
  4. EMPTY → TREE with probability pgrowth.

Sweeping the tree density reveals a percolation threshold near 0.59 for a square lattice: below it fires die out, above it they cross the whole grid. Firebreak spacing policies are then evaluated as a shift of that threshold.

Other established uses: traffic flow (Nagel–Schreckenberg model reproduces phantom jams), lattice-gas and lattice-Boltzmann fluid models, urban growth (SLEUTH), crystal growth, tumour growth, and image processing.

6.4 CA versus ABM

Table 2.5 — Cellular automata compared with agent-based models.
Aspect Cellular automaton Agent-based model
Entity A fixed cell of space A mobile individual
Mobility Cells never move; only states change Agents move through the environment
Rules Identical for all cells May differ per agent (heterogeneous)
State Finite, usually very small Arbitrarily rich, with memory and goals
Update Synchronous by definition Often asynchronous or event-driven
Cost Very cheap; trivially parallel Expensive; parallelism needs care
Common mistake

Updating a CA in place. Because the rule is defined on the previous configuration, you must write into a second array and swap. In-place updating silently produces a different (asynchronous) model — Game of Life, for instance, stops producing gliders.

7. Monte Carlo and Probabilistic Simulations

Definition

A Monte Carlo method estimates a numerical quantity by drawing repeated random samples and averaging a function of them; by the law of large numbers the sample mean converges to the expectation, and by the central limit theorem the error decreases as σ/√n.

I = ∫ g(x)p(x) dx = E[g (X)]  ≈  În = (1/n) ∑i=1n g(Xi),    Xi ~ p

7.1 The canonical illustration

Example — estimating π (your Experiment 6)

Sample n points uniformly in the unit square, count the fraction m/n falling inside the quarter circle x2+y2 ≤ 1; then π ≈ 4m/n. Since the indicator is Bernoulli with p = π/4, the standard error of the estimate is 4√(p(1−p)/n) ≈ 1.64/√n. To get two correct decimal places (error 0.005) you need roughly 105 samples; for four decimals, 109. This is the practical meaning of “slow but dimension-free convergence”.

7.2 Why Monte Carlo wins in high dimensions

A deterministic quadrature rule on a grid needs O(Nd) points in d dimensions — the curse of dimensionality. The Monte Carlo error σ/√n does not depend on d at all. Above roughly four dimensions Monte Carlo is the only practical choice, which is why it dominates finance, particle physics, Bayesian statistics and rendering.

7.3 Variance reduction

  1. Antithetic variates — pair each u with 1−u so that errors cancel through negative correlation.
  2. Control variates — subtract a correlated quantity whose expectation is known.
  3. Importance sampling — sample from a distribution that emphasises the important region and reweight; the essential technique for rare-event estimation.
  4. Stratified sampling / Latin hypercube — force coverage of every region of the input space.
  5. Common random numbers — when comparing two systems, drive both with the same random stream so the difference has lower variance.
  6. Quasi-Monte Carlo — low-discrepancy sequences (Sobol, Halton) giving O((log n)d/n) for smooth integrands.

7.4 Markov chain Monte Carlo and related methods

When direct sampling from the target distribution is impossible, construct a Markov chain whose stationary distribution is the target: Metropolis–Hastings, Gibbs sampling, Hamiltonian Monte Carlo. Related stochastic-simulation algorithms include Gillespie's SSA for exact chemical-reaction trajectories and simulated annealing for optimisation. Diagnostics (burn-in, autocorrelation time, effective sample size, multiple chains) are compulsory — MCMC samples are not independent, so the naive confidence interval is wrong.

Exam tip

Monte Carlo questions almost always want four things: the estimator formula, the σ/√n error law, the dimension-independence argument, and two variance reduction techniques described properly. Add the π example with its numbers and the answer is complete.

8. Event-Driven Simulation Architectures

Section 2 of Unit I introduced the event mechanism. Here we look at how a simulator is architected around it.

8.1 The three classical world views

Table 2.6 — World views for organising a discrete-event model.
World view Modeller writes Engine does
Event scheduling An event routine per event type, each scheduling future events Pops the earliest event and calls its routine
Process interaction The life cycle of an entity as a sequential process with waits (SimPy's yield) Suspends and resumes coroutines at the right simulated times
Activity scanning Activities with start conditions Advances time, then rescans all conditions for activities that can now start

8.2 Components of an event-driven engine

  1. Future event list. The performance-critical structure. A binary heap gives O(log n) insert and extract-min; calendar queues and ladder queues achieve amortised O(1) for typical simulation workloads.
  2. Event dispatcher. Pops the minimum timestamp, updates the clock, invokes the handler; enforces a deterministic tie-break rule.
  3. State manager. Entities, resources, queues; optionally with checkpointing for rollback (Time Warp, Unit III).
  4. Random number service. Independent, reproducible substreams per entity, so that adding one entity does not perturb every other entity's random draws.
  5. Statistics collector. Time-weighted averages (queue length) and observation-based averages (waiting time), with warm-up truncation and batch means.
  6. Trace / logging subsystem. The main verification tool: an event trace that a human can read line by line.
Definition — Zero-delay (simultaneous) events

Events scheduled at the same simulated time form a delta cycle. Their relative order can change the result, so the engine must define a deterministic priority. A cycle of zero-delay events that keeps rescheduling itself is a zero-time loop and hangs the simulation while the clock never advances.

8.3 Architectural variants

9. Simulations of Complex Adaptive Systems

Definition

A complex adaptive system (CAS) is a system of many interacting components that adapt or learn from experience, in which the system-level behaviour emerges from local interactions, is not predictable by analysing the components in isolation, and feeds back to shape the components themselves.

9.1 Hallmarks of a CAS

  1. Emergence — macro patterns from micro rules.
  2. Adaptation and learning — agents change their rules in response to outcomes.
  3. Nonlinearity — effects are not proportional to causes; small changes may produce large consequences.
  4. Feedback loops — reinforcing (positive) and balancing (negative).
  5. Self-organisation — order without a central controller.
  6. Path dependence and history — the outcome depends on the sequence of events, not only on the parameters.
  7. Tipping points and phase transitions — qualitative change at a critical parameter value.
  8. Robustness with fragility — tolerant of random damage, vulnerable to targeted damage (scale-free networks again).

9.2 Why simulation is the method of choice

CAS are analytically intractable by construction: heterogeneity, nonlinearity, adaptation and network structure all break the assumptions behind closed-form solutions. Simulation is used as generative science: “if you did not grow it, you did not explain it” (Epstein). A mechanism is accepted when a model built only from plausible local rules reproduces the observed macro pattern.

9.3 Examples and modelling of critical infrastructure

Example — cascading failure in an interdependent network

Two coupled networks: a power grid and a communication network, with each power node depending on a comms node and vice versa. Remove a small fraction 1−p of power nodes at random. Nodes whose support in the other layer is gone also fail, which removes further support, and so on. Unlike a single network, whose giant component shrinks continuously, coupled networks show a first-order (abrupt) collapse at a critical pc . This is the standard demonstration that interdependence itself creates fragility.

9.4 Analysing CAS output

10. Domain-Specific Simulation Applications

The final syllabus item asks you to connect paradigms to domains. Learn the table below as a mapping exercise; examiners frequently ask “which paradigm would you use for X, and why?”

Table 2.7 — Domains, dominant paradigm and representative tools.
Domain Typical paradigm Questions answered / tools
Computer networks Discrete event + packet-level queues Throughput, latency, loss under protocols; ns-3, OMNeT++, Mininet
Computer architecture Cycle-accurate event-driven IPC, cache miss rate, energy; gem5, Sniper
Manufacturing & logistics Discrete event (process interaction) Throughput, WIP, bottlenecks, buffer sizing; Arena, FlexSim, Simul8
Transport & traffic CA or agent based (micro), fluid (macro) Congestion, signal timing, evacuation; SUMO, VISSIM, MATSim
Epidemiology & public health Compartmental ODE, network, agent based Peak load, intervention timing, contact tracing; EpiModel, FRED, Covasim
Power systems Continuous (DAE) + event (protection relays) Stability, cascading outage, FACTS device placement; PSS®E, PowerFactory, PSCAD
Fluids, structures, climate Mesh based (FVM/FEM), parallel Drag, stress, forecast fields; OpenFOAM, ANSYS, WRF
Finance & risk Monte Carlo, SDEs, agent based Option pricing, VaR, flash-crash mechanisms
Molecular & systems biology Particle MD, Gillespie SSA, ODE Binding, kinetics, pathway dynamics; GROMACS, LAMMPS, COPASI
Robotics & autonomy Continuous physics + multi-agent Control validation, sim-to-real transfer; Gazebo, CARLA, Isaac Sim
Exam tip — how to justify a paradigm choice

Answer in four moves: (1) what is the entity and does its identity matter? (2) what is the coupling — edges, messages, geometry, or none? (3) is activity dense (time-step) or sparse (events)? (4) what does the decision-maker need — a mean, a distribution, or a mechanism? Then name the paradigm and one tool.

11. Unit Summary

11.1 Key terms

Node transition rule · degree distribution · epidemic threshold · small world · scale free · actor · mailbox · location transparency · structured and unstructured mesh · FDM/FVM/FEM · CFL condition · halo exchange · hybrid simulation · system dynamics · emergence · stigmergy · BDI · ODD protocol · von Neumann and Moore neighbourhoods · Wolfram classes · percolation threshold · importance sampling · MCMC · calendar queue · delta cycle · DEVS · complex adaptive system · cascading failure.

11.2 Practice questions

Short answer (2–3 marks each)

  1. Define a cellular automaton by its four components.
  2. State the three actions an actor may take on receiving a message.
  3. What is emergence? Give one example.
  4. Why is Monte Carlo error independent of dimension?
  5. Differentiate structured and unstructured meshes.
  6. What is a delta cycle, and why must simultaneous events be ordered deterministically?
  7. Name two properties that make a system a complex adaptive system.

Medium answer (5 marks each)

  1. Describe a network-based SIR simulation and explain how network topology affects the epidemic threshold.
  2. Compare cellular automata with agent-based models under at least five criteria.
  3. Explain the three world views of discrete-event simulation with one example each.
  4. Describe two variance reduction techniques and state when each is appropriate.
  5. Explain, with an example, why a hybrid simulation may be preferred to a single-paradigm model, and list the interface problems it introduces.

Long answer (10 marks each)

  1. Explain agent-based and multi-agent simulation in detail: agent properties, architectures, coordination mechanisms, emergence, strengths, limitations and reporting standards.
  2. Explain mesh-based simulation from mesh generation to solution: mesh types, discretisation methods, boundary conditions, stability conditions and convergence studies.
  3. Design a cellular-automaton simulation of forest-fire spread. Give states, neighbourhood, rules, parameters, boundary conditions, observables, and describe the percolation behaviour observed as density varies.
  4. Discuss simulation of complex adaptive systems, using interdependent critical infrastructure as the case study; include emergence, cascading failure and how such results should be analysed.
  5. Survey domain-specific simulation applications, and justify the dominant paradigm in each of five domains.

11.3 Further reading

← Unit I: Simulation Basics Unit III: Parallel and Distributed Simulations →
CSEG8003 Modelling and Simulation · Unit II student notes · Dr. Mohsin Furkh Dar · UPES